public class Test27 {
    public static TreeNode convert(TreeNode root){
        TreeNode[] lastNode = new TreeNode[1];
        convertTreeNode(root,lastNode);
        TreeNode head = lastNode[0];
        //找到头节点
        while(head != null && head.left !=null){
            head = head.left;
        }
        return head;

    }
    public static void convertTreeNode(TreeNode node,TreeNode[] lastNode){
        if (node != null){
            //先处理左子树
            if (node.left != null) convertTreeNode(node.left,lastNode);//寻找左子树
            node.left = lastNode[0];//将当前节点的前驱节点，指向已经处理好的双向链表的尾节点
            if (lastNode[0] != null)//把处理好的尾节点的右指针指向node
                lastNode[0].right = node;
            //记录这个节点
            lastNode[0] = node;
            if (node.right != null) convertTreeNode(node.right,lastNode);

        }
    }

    public static void printTreenode(TreeNode root){
        TreeNode temp = root;
        if(temp != null){
            printTreenode(temp.left);
            System.out.print(temp.val + " ");
            printTreenode(temp.right);
        }
    }
    public static void printList(TreeNode head){
        TreeNode temp = head;
        while(temp != null){
            System.out.print(temp.val + " ");
            temp = temp.right;
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode();
        root.val = 1;
        root.left = new TreeNode();
        root.left.val = 2;
        root.right = new TreeNode();
        root.right.val = 3;
        root.left.left = new TreeNode();
        root.left.left.val = 4;
        root.left.right = new TreeNode();
        root.left.right.val = 5;
        root.right.left = new TreeNode();
        root.right.left.val = 6;
        root.right.right = new TreeNode();
        root.right.right.val = 7;

        printTreenode(root);
        System.out.println();
        TreeNode node = convert(root);
        printList(node);
    }

}
